/**
 * 
 */

/**
 * @author TrinhNX
 * @start_date	: 2015/05/13
 * @end_date 	:
 */
public class Dynamic {
	private static int[] memoi;

	public static void main(String[] args) {
		Dynamic dm = new Dynamic();
		final int fib_num = 10;
		memoi = new int[fib_num + 1];
		memoi[0] = 0;
		memoi[1] = 1;
		// Worst
		long start = System.currentTimeMillis();
		System.out.println(dm.recurFibo(fib_num));
		System.out.println("End after: " + (System.currentTimeMillis() - start));
		// Case #1
		start = System.currentTimeMillis();
		System.out.println(dm.memoiFibo(fib_num));
		System.out.println("End after: " + (System.currentTimeMillis() - start));
		// Case #2
		start = System.currentTimeMillis();
		System.out.println(dm.interFibo(fib_num));
		System.out.println("End after: " + (System.currentTimeMillis() - start));
		// Case #3
		start = System.currentTimeMillis();
		System.out.println(dm.interBetterFibo(fib_num));
		System.out.println("End after: " + (System.currentTimeMillis() - start));
		
		dm.coinSum(3);

	}

	// Definition
	private int recurFibo(final int n) {
		if (n < 2) {
			return n;
		} else {
			return (recurFibo(n - 1) + recurFibo(n - 2));
		}
	}

	// Memoization simple
	// Store value
	private int memoiFibo(final int n) {
		if (n < 2) {
			return memoi[n];
		} else {
			if (memoi[n] == 0) {
				memoi[n] = memoiFibo(n - 1) + memoiFibo(n - 2);
			}
			return memoi[n];
		}
	}

	private int interFibo(final int n) {
		memoi[0] = 0;
		memoi[1] = 1;
		for (int i = 2; i < n; i++) {
			memoi[i] = memoi[i - 1] + memoi[i - 2];
		}
		return memoi[n];
	}

	private int interBetterFibo(final int n) {
		int prev = 1;
		int curr = 0;
		int next;
		for (int i = 0; i < n; i++) {
			next = prev + curr;
			prev = curr;
			curr = next;
		}
		return curr;
	}

	static int[] array = { 1, 2 };

	private void coinSum(final int sum) {
		int[] available = new int[sum];
		available[0] = 1;

		for (int i = 0, length = array.length; i < length; i++) {
			for (int j = array[i]; j < sum; j++) {
				available[j] += available[j - array[i]];
			}
			Common.printArray(available, "\t");
			System.out.println();
		}

	}

}
